//
//  SortSequence.h
//  iOS-Learning-Demo
//
//  Created by yuan xiaodong on 2022/3/21.
//  Copyright © 2022 yuan. All rights reserved.
//

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface SortSequence : NSObject

/**
 //TODO:冒泡算法
 从大到小:4426.133037 ms
 从小到大:4434.162021 ms
 
 平均时间复杂度：O(n2)
 空间复杂度：O(1) (用于交换)
 稳定性：稳定
 */
+ (NSArray *)sortByMaoPao:(NSArray *)arr desc:(BOOL)desc;
+ (void)sortByMaoPao;

/**
 //TODO:直接选择排序
 从大到小:4389.441967 ms
 从小到大:4222.674012 ms
 
 时间复杂度：O(N^2)
 空间复杂度：O(1)
 稳定性：不稳定
 内部排序
 
 思想：第一次从 V[0]~V[n-1] 中选取最小值，与V[0]交换，第二次从 V[1]~V[n-1] 中选取最小值，与V[1]交换,...,第 i 次从 V[i-1]~V[n-1] 中选取最小值，与V[n-2]交换，总共通过 n-1 次，得到一个按从小到大的有序排列。
 */
+ (NSArray *)sortBySelect:(NSArray *)arr desc:(BOOL)desc;
+ (void)sortBySelect;
/**
 //TODO:直接插入排序
 从大到小:3537.160993 ms
 从小到大:3093.631983 ms
 
 时间复杂度O(n^2)
 控件复杂度O(1)
 稳定性： 稳定
 内部排序
 
 思想：当插入第i(i>=1)个元素时，前面的V[0],...,V[i-1]个元素已经有序。这时，将第i个元素和前i-1个元素V[i-1],...,V[0]依次比较，找到插入的位置即将V[i]插入，同时原来位置上的元素向后顺移。
 */
+ (NSArray *)sortByInsert:(NSArray *)arr desc:(BOOL)desc;
+ (void)sortByInsert;

/**
 //TODO:折半插入排序(二分法)
 从大到小:785.764933 ms
 从小到大:763.529897 ms
 
 时间复杂度：O(N^2)
 稳定性：稳定
 内部排序
 
 思想：当插入第 i (i >= 1)时，前面的V[0],...,V[i-1]等 i-1 个元素已经有序。这时，折半搜索第 i 个元素在前 i-1 个元素V[i-1],...V[0]中的插入位置，然后将V[i]插入，同时原来位置上的元素向后顺移。与直接插入排序不同的是，折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（N^2），但其减少了比较次数，所以该算法仍然比直接插入排序好。折半插入排序是一种稳定的排序算法。实现如下：
 */
+ (NSArray *)sortByHalf:(NSArray *)arr desc:(BOOL)desc;
+ (void)sortByHalf;

/**
 //TODO:希尔排序
 从大到小:5833.813071 ms
 从小到大:5741.113901 ms
 
 时间复杂度：O(n) ~ O(n^2)
 空间复杂度：O(1)
 稳定性：不稳定
 内部排序
 
 思想：假设待排序的元素共 N 个元素，首先取一个整数 i<n 作为间隔，将全部元素分为间隔为 i 的 i 个子序列并对每个子序列进行直接插入排序。然后缩小间隔 i ，重复上述操作，直至 i 缩小为1，此时所有的元素位于同一个序列且有序。由于刚开始时 i 较大， 每个子序列元素较少，排序速度较快。后期 i 变小，每个子序列元素较多，但大部分元素有序，所以排序速度仍然较快。一般 i 取 i/2。 希尔排序是一种不稳定的排序算法。实现如下
 */
+ (NSArray *)sortByShell:(NSArray *)arr desc:(BOOL)desc;
+ (void)sortByShell;

/**
 //TODO:堆排序
 从大到小:37.944078 ms
 从小到大:47.698975 ms
 
 时间复杂度：O(n) ~ O(n^2)
 空间复杂度：O(1)
 稳定性：不稳定
 内部排序
 
 思想：堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部
 */
+ (NSArray *)sortByStack:(NSArray *)arr desc:(BOOL)desc;
+ (void)sortByStack;

/**
 //TODO:快速排序

 从大到小:11.417031 ms
 从小到大:12.031078 ms
 
 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小(划分过程)，然后再按此方法对这两部分数据分别进行快速排序(快速排序过程)，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是一种不稳定的排序算法
 */
+ (NSArray *)sortByQuite:(NSArray *)arr desc:(BOOL)desc;
+ (void)sortByQuite;

/**
 //TODO:归并排序
 
 从大到小:52.412987 ms ms
 从小到大:59.804082 ms
 
 思想：其中，”归”是指将原序列分成半子序列，分别对子序列进行递归排序；”并”是指将排好序的各子序列合并成原序列。归并排序算法是一个典型的递归算法，因此也是概念上最为简单的排序算法。与快速排序算法相比，归并排序算法不依赖于初始序列，并且是一种稳定的排序算法，但需要与原序列一样大小的辅助存储空间。
 
 */
+ (NSArray *)sortByMerge:(NSArray *)arr desc:(BOOL)desc;
+ (void)sortByMerge;

@end

NS_ASSUME_NONNULL_END
